package algorithm.algorithm4.sort;

import java.util.ArrayList;
import java.util.List;

public class Sort {
	@SuppressWarnings("rawtypes")
	private static List<Comparable> guibing_aux;//避免每次归并重复申请
	public static void main(String[] args) {
		int size=(int) Math.pow(2, 18);
		int T = 1;
		while(size<Math.pow(2, 25))
		{
			SortUtils.performance(size,T);
			size*=2;
		}
//		SortUtils.test("quick_3way",100);
		System.out.println("over!");
	}
	public static <T extends Comparable<T>> void select_sort(List<T> arr)
	{//选择排序
		for(int i=0; i<arr.size(); i++)
		{
			int idx_min=i;
			for(int j=i+1; j<arr.size(); j++)
				if(arr.get(j).compareTo(arr.get(idx_min))<0)
					idx_min=j;
			SortUtils.swap(arr, i, idx_min);
		}
	}
	public static <T extends Comparable<T>> void insert_sort(List<T> arr)
	{//i下标左边的都是有序的，将arr[i]插入到左边的有序数组中
		//改进：避免每次都交换，而是将大的往右边移动
		for(int i=1;i<arr.size();i++)
		{
			for(int j=i;j>0;j--)
			{
				if(arr.get(j).compareTo(arr.get(j-1))>=0)
					break;
				SortUtils.swap(arr, j, j-1);
			}
		}
	}
	public static <T extends Comparable<T>> void insert_sort_ex(List<T> arr)
	{//i下标左边的都是有序的，将arr[i]插入到左边的有序数组中
		//改进：避免每次都交换，而是将大的往右边移动
		for(int i=1;i<arr.size();i++)
		{
			T tmp=arr.get(i);
			int j;
			for(j=i;j>0;j--)
			{
				if(tmp.compareTo(arr.get(j-1))<0)
					arr.set(j, arr.get(j-1));
				else break;
			}
			arr.set(j, tmp);
		}
	}
	public static <T extends Comparable<T>> void shell_sort(List<T>arr)
	{//希尔升序排序，可以认为是插入排序的改进,h有序数组，h如何选择？
		int N = arr.size();
		int h = 1;
		while(h<N/3)	h = 3*h+1;//算法4书中的一种选择方案，网上有些人选择以2为倍数，应该是根据数组大小
		while(h>=1)
		{
			for(int i=h;i<arr.size();i++)
			{
				T tmp = arr.get(i);
				int j;
				for(j=i;j>=h;j-=h)
				{
					if((tmp.compareTo(arr.get(j-h)))<0)
						arr.set(j, arr.get(j-h));
					else	break;
				}
				arr.set(j, tmp);
			}
			h/=3;
		}
	}
	public static <T extends Comparable<T>> void guibing_sort(List<T> arr) {
		// 自上而下的归并排序，递归
		Sort.guibing_aux = new ArrayList<>(arr);
		guibing_sort_recurrence(arr, 0, arr.size()-1);
	}
	private static <T extends Comparable<T>> void guibing_sort_recurrence(List<T>arr,int lo,int hi)
	{
		if(lo>=hi)	return;
		int mid = lo+(hi-lo)/2;
		guibing_sort_recurrence(arr, lo, mid);
		guibing_sort_recurrence(arr, mid+1, hi);
		guibing_sort_merge(arr, lo, mid+1, hi);
	}
	@SuppressWarnings("unchecked")
	private static <T extends Comparable<T>> void guibing_sort_merge(List<T>arr,int lo,int mid,int hi)
	{
		for(int i=lo;i<=hi;i++)
			Sort.guibing_aux.set(i, arr.get(i));//复制
		int i=lo,j=mid;
		for(int k=lo;k<=hi;k++)
		{
			if(i>=mid)	arr.set(k, (T) Sort.guibing_aux.get(j++));
			else if(j>hi)	arr.set(k, (T) Sort.guibing_aux.get(i++));
			else if(Sort.guibing_aux.get(i).compareTo(Sort.guibing_aux.get(j))>0)
				arr.set(k, (T) Sort.guibing_aux.get(j++));
			else
				arr.set(k, (T) Sort.guibing_aux.get(i++));
		}
	}
	public static <T extends Comparable<T>> void guibing_sort_BU(List<T>arr)
	{//自下而上的归并排序
		Sort.guibing_aux = new ArrayList<>(arr);
		int N = arr.size();
		for(int sz=1;sz<N;sz=2*sz)//sz子数组长度
			for(int j=0;j+sz<N;j+=2*sz)
				guibing_sort_merge(arr, j, j+sz, Math.min(j+2*sz-1, N-1));
	}
	public static <T extends Comparable<T>> void quick_sort(List<T>arr)
	{
		quick_sort_sub(arr, 0, arr.size()-1);
	}
	private static <T extends Comparable<T>> void quick_sort_sub(List<T>arr,int lo,int hi)
	{
		if(lo>=hi)	return;
		int p = quick_sort_partition(arr, lo, hi);
		quick_sort_sub(arr, lo, p-1);
		quick_sort_sub(arr, p+1, hi);
	}
	private static <T extends Comparable<T>> int quick_sort_partition(List<T>arr,int lo,int hi)
	{
		int i=lo,j=hi+1;
		T p = arr.get(lo);
		while(true)
		{
			while(arr.get(++i).compareTo(p)<0)	//当遇到和切分值相同的元素时，继续扫描还是停下来？选择停下来！尽管这会造成一些比必要的交换，否则快排可能变成O(n2)
				if(i>=hi)	break;
			while(arr.get(--j).compareTo(p)>0)	
				if(j<=lo)	break;//注意，这里需要比到lo的位置，而不是lo+1
			if(i>=j)	break;
			SortUtils.swap(arr, i, j);
		}
		SortUtils.swap(arr, lo, j);
		return j;
	}
	public static <T extends Comparable<T>> void quick_sort_3way(List<T>arr)
	{
		quick_sort_3way(arr, 0, arr.size()-1);
	}
	private static <T extends Comparable<T>> void quick_sort_3way(List<T>arr,int lo,int hi)
	{
		if(hi<=lo)	return;
		int lt=lo,i=lo+1,gt=hi;
		T v = arr.get(lo);
		while(i<=gt)
		{
			int cmp = arr.get(i).compareTo(v);
			if(cmp<0)	SortUtils.swap(arr, lt++, i++);
			else if(cmp>0)	SortUtils.swap(arr, i, gt--);
			else	i++;
		}
		quick_sort_3way(arr, lo, lt-1);
		quick_sort_3way(arr, gt+1, hi);
		
	}
}